﻿// 光学字符识别 OCR.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
/*
https://algospot.com/judge/problem/read/OCR

问题
提示：由于评分服务器速度问题，将时间限制增加至60秒，并将测试用例数量减少至20个。

光学字符识别（Optical Character Recognition）是将人们手写或机器打印的文字扫描图像转换为机器可读的字符的过程。OCR算法通常通过统计分析大量手写样本并找到模式来识别每个单词。然而，考虑到单词的分布和语法等因素，与简单地逐个识别单词相比，往往可以获得更好的结果。在这个问题中，让我们利用从过去的数据中提取的信息来提高字符识别的准确性。

我们希望通过分析过去识别的许多句子来了解原始句子的形式。为此，首先我们创建了过去数据中出现的所有单词列表，然后计算了每个单词作为句子的第一个单词出现的比例。接下来，对于每对单词，我们计算了一个单词紧跟另一个单词出现的概率。假设我们要识别的原始句子具有与过去数据相同的分布。换句话说，假设只要有这个概率表，我们就能准确计算任何原始句子出现的概率。

我们的字符识别算法将原始图像切分成多个片段，然后将每个片段分类为相似的单词。这个用于分类的算法被称为分类器（classifier）。由于分类器并不完美，它可能会将某个单词错误地识别为另一个单词。例如，可能会将"boy"错误识别为"buy"或"bay"。我们测试了许多示例输入，对于每个单词片段，我们测试了分类器的输出以及每个识别结果的概率。例如，当将实际上写有"boy"的片段输入给分类器时，正确识别为"boy"的概率是0.7，识别为"bay"的概率是0.25，识别为"buy"的概率是0.04，识别为"bye"的概率是0.01。

有了这些信息，我们可以进行更好的字符识别。假设我们使用前面提到的分类器将每个片段识别为"I am a bay."这个句子。然而，在查看数据之后，我们发现在"a"之后出现"bay"的概率很低，而在"a"之后出现"boy"的概率非常高。假设我们的分类器将识别为"bay"的片段实际上应该是"boy"的概率为0.25，那么将该句子的识别结果更正为"I am a boy."将是更正确的分类。

给定按单词进行识别的结果，编写一个程序找到具有最高条件出现概率的原始句子。

输入
输入由过去数据的统计信息和分类器识别的句子组成。

第一行包含可出现在原始句子中的单词数量m（1≤m≤500）以及要处理的句子数量q（1≤q≤20）。
第二行包含m个单词，用空格分隔。每个单词只由大写或小写字母组成，所有单词的长度不超过10。
第三行包含m个实数B[i]，表示第i个单词作为首个单词出现的概率。所有B[i]的总和为1。
接下来的m行是一个大小为m×m的实数矩阵T。矩阵中第i行第j列的数字T[i, j]表示第i个单词的下一个单词是第j个单词的概率。每行中的概率之和始终为1。
之后的m行是一个大小为m×m的实数矩阵M。矩阵中第i行第j列的数字M[i, j]表示将标记为第i个单词的片段分类为第j个单词的概率。每行中的概率之和始终为1。
最后有q行，每行包含一个分类器识别出的句子。每行的开头是单词的数量n（1≤n≤100），之后是n个单词，表示分类器的识别结果。所有单词都是最初给定的m个单词中的一个。

对于每个句子，在一行中输出具有最高条件概率的句子结果。如果给定输入中有多个具有最高概率的句子，可以输出其中任意一个。


5 3
I am a boy buy
1.0 0.0 0.0 0.0 0.0
0.1 0.6 0.1 0.1 0.1
0.1 0.1 0.6 0.1 0.1
0.1 0.1 0.1 0.6 0.1
0.2 0.2 0.2 0.2 0.2
0.2 0.2 0.2 0.2 0.2
0.8 0.1 0.0 0.1 0.0
0.1 0.7 0.0 0.2 0.0
0.0 0.1 0.8 0.0 0.1
0.0 0.0 0.0 0.5 0.5
0.0 0.0 0.0 0.5 0.5
4 I am a buy
4 I I a boy
4 I am am boy


I am a boy
I am a boy
I am a boy
*/
int main()
{
    std::cout << "Hello World!\n";
}

 